home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 011 / btree.cq / btree.c
Encoding:
C/C++ Source or Header  |  1985-01-28  |  11.1 KB  |  419 lines
  1. /*
  2.     B-SORT        A sorting program using the B-tree algorithm
  3.     VRS 1.12   2-AUG-82        J.Riley
  4.  
  5.     This is a self-contained file except for the standard included
  6.     definitions and is part of the  larger development of a message-
  7.     retrieval system. Since the algorithms involved are well known
  8.     it is felt that putting this program in public domain would serve
  9.     a useful purpose, namely provide some examples of some programming
  10.     techniques using the 'C' language. The compiler used is the BDS
  11.     vs 1.46 and use is made of at least one special feature of this
  12.     compiler(see 'printf' function).
  13.  
  14.     Nominally this is a sorting program and can certainly be used for
  15.     that purpose. However, since the main benefit of using a B-tree is
  16.     when using disk-based structures, it is quite possible that this
  17.     will not be your hot-dog sort utility. It is relatively fast though
  18.     and I would be interested in any comparisons anyone makes. A later
  19.     effort is planned to build a virtual memory support package which
  20.     will then allow the 'nodes' of the b-tree to be stored as disk
  21.     sectors and at that point this program will allow sorting of
  22.     arbitrarily large text files. Again, that is still not the main
  23.     objective for it, information retrieval is.
  24.  
  25.     An introduction to the B-tree concept is not attempted here. The
  26.     primary reference and, in fact, the bareface source of this program
  27.     is N. Wirth's wonderful book "Algorithms+Data Structures=Programs".
  28.     I passed this book up several times in the past, but when I was 
  29.     looking for a treatment of this subject, I found that it had a very
  30.     nice balance between explanation and example(the best way I learn)
  31.     and since 'C' and PASCAL are 'kissin cousins', it was 'straight
  32.     forward' to do the transcribing. So go to god and read section
  33.     4.51 if you want to understand what is going on here. Also you can
  34.     get a little contrast of the styles which result from the different
  35.     features of the two languages(especially w re pointer variables).
  36.  
  37.     Things to note in this program which you may not already be
  38.     familiar with are the following:
  39.  
  40.         1) A nested data structure(PAGE) is used. This is possible
  41.            in PASCAL and PL/I too and makes life a lot more pleasant.
  42.            Try doing the same thing in BASIC or FORTRAN, what a
  43.            mess! In a sense it would be easier in assembler.
  44.  
  45.         2) Note that the tree structure used is a balanced one
  46.            so that no single branch gets long at the expense of
  47.            others. To see the depth level of the tree, turn on
  48.            the SPRINT parameter and note the first column of the
  49.            output on any sort. There is a trade-off here, though
  50.            in that it takes longer to build the tree than if it
  51.            were just a binary tree(not an AVL though). Thats why
  52.            b-trees are best for retrieval rather than simple
  53.            sorts.
  54.  
  55.         3) The logic uses a rather interesting recursive structure
  56.            in which 'emerging' items are handed back through higher
  57.            levels until perhaps to the root of the tree. See the
  58.            variable called 'u' in function 'search'.
  59.  
  60.         4) The parameter KEYPTR allows the option of including the
  61.            string storage area in the nodes themselves as opposed
  62.            to allocated areas. The latter is faster since no move-
  63.            ment of strings is necessary after they have been given
  64.            initial allocations. However, for disk-based use the
  65.            strings(keys) would need to be in the nodes. To see the
  66.            difference in performance(big!) just undefine(comment
  67.            out) this parameter.
  68.  
  69.         5) One peculiarity of the 'C' language came up in an earlier
  70.            version of B-sort, it would not sort itself! Clue, this
  71.            had to do with the way that 'printf' works. See if you
  72.            can figure out how this happened and how it was fixed.
  73.  
  74.     I hope this program is useful for some in learning more about the
  75.     'C' language and an interesting algorithm(the key to better software).
  76.     If you make any improvements give me a copy. If you mutilate it, keep
  77.     it to yourself.
  78.                 Jack Riley (303) 499-9169 RCPM, Boulder, CO.
  79. */
  80.  
  81. #include "bdscio.h"    /* version with ALLOC_ON false*/
  82.  
  83. #DEFINE N        2  /* half-size of b-tree node */
  84.  
  85. /* options for customizing the program */
  86.  
  87. /* #DEFINE SPRINT */         /* provides statistics on keys in output */
  88. #DEFINE KEYPTR        /* uses pointer references to strings instead of
  89.                arrays in the b-tree nodes */
  90. /* #DEFINE DIAGNOSE */    /* turns on voluminous trace information on actions
  91.                taken by program logic.. perhaps instructive */
  92. /* special assigned values */
  93.  
  94. #DEFINE alloc        sbrk /* only need simple allocation method */
  95. #DEFINE KEYSIZE        80
  96. #DEFINE MAX_LEN        20
  97. #DEFINE MAXPRINT    3000
  98.  
  99. /* dependent parameters */
  100.  
  101. #DEFINE NN        N+N
  102. #DEFINE NM1        N-1
  103. #DEFINE NM2        N-2
  104. #DEFINE    NP1        N+1
  105.  
  106. /* structure definitions */
  107.  
  108. #DEFINE ITEM         struct sitem
  109. #DEFINE PAGE         struct spage
  110.  
  111. ITEM {
  112. #ifndef KEYPTR
  113.     CHAR KEY[KEYSIZE];
  114. #endif
  115. #ifdef KEYPTR
  116.     CHAR *KEY;
  117. #endif
  118.     PAGE *P;
  119. #ifdef SPRINT
  120.     UNSIGNED COUNT;
  121. #endif
  122.     } oneitem;
  123.  
  124. PAGE {
  125.     UNSIGNED M;
  126.     PAGE *P0;
  127.     ITEM E[NN];
  128.     } onepage;
  129.  
  130. /* external variables */
  131.  
  132. PAGE *root,*q;
  133. ITEM g;
  134. FILE infile,l_buffer;
  135. CHAR infilnam[MAX_LEN], instrg[MAXLINE], o_flg;
  136. INT sizitem,sizpage, maxcount, nkeys, tokcount;
  137.  
  138. /* beginning of programs */
  139.  
  140. use_err() /* Usage message: */
  141.  
  142.        { printfc("\nERROR: Invalid parameter specification\n\n");
  143.        printfc("Usage: b-sort(vr 1.12) <filename> <flag(s)>\n\n");
  144.        printfc("       -o <filename> = Write output to named file\n");
  145.        exit(0); }
  146.  
  147. main(argc,argv)
  148. int argc;
  149. char **argv;
  150. {
  151.     char *arg;
  152.  
  153.     o_flg=FALSE;        /* output file flag */
  154.  
  155.     if (argc < 2) use_err();
  156.  
  157.     strcpy(infilnam,*++argv);
  158.  
  159.     if( fopen(infilnam,infile) == ERROR )
  160.         { printfc("\nERROR: Unable to open input file: %s\n",infilnam);
  161.           EXIT(0); }
  162.  
  163.     if(--argc > 0)
  164.        if(*(arg=*++argv) == '-')
  165.         if(tolower(*++arg) == 'o')
  166.             { o_flg++;
  167.             if(--argc == 0)
  168.                 {printfc("\nneed output file name");use_err();}
  169.             if(fcreat(*++argv,l_buffer) == ERROR)
  170.              {printfc("ERROR: Unable to create output file - %s\n",
  171.                         *argv); exit(0);}
  172.             }
  173.  
  174.     root=NULL; sizitem=sizeof(oneitem); sizpage=sizeof(onepage);
  175.     tokcount=nkeys=0;
  176.  
  177. #ifdef DIAGNOSE
  178.     printf("\n&root=%x,g=%x,sizi=%d,sizp=%d",&root,g,sizitem,sizpage);
  179. #endif
  180.  
  181.     while( fgets(instrg,infile) )
  182.         {
  183.         if( trim(instrg) <= 0 ) continue;
  184.  
  185.         instrg[KEYSIZE-1]='\0';
  186.  
  187. #ifdef DIAGNOSE
  188.         printf("\n\nsearch key= %s",instrg);
  189. #endif
  190.         if( search(instrg,root,g) )
  191.             { q=root; 
  192.              if( (root=alloc(sizpage)) == ERROR)
  193.                 { printfc("\nERROR unable to allocate page");
  194.                   EXIT(0); }
  195. #ifdef DIAGNOSE
  196. printf("  root=%x, q=%x",root,q);
  197. #endif
  198.  
  199.             root->M=1; root->P0=q; movmem(g, root->E[0] , sizitem);
  200.  
  201.             }
  202.         }
  203.  
  204.     printfc("\nEnd of input\n");
  205.  
  206.     printfc("\nnumber of unique keys=%d, total key count=%d\n",
  207.                     nkeys,tokcount);
  208.     if(!o_flg) pause();
  209.  
  210.     maxcount=MAXPRINT; printtree(root,1);
  211.  
  212.     printf("\n");
  213.     if(o_flg)
  214.         { putc(CPMEOF,l_buffer); fflush(l_buffer); fclose(l_buffer); }
  215. }
  216. CHAR search(x,a,v)
  217. CHAR *x;
  218. PAGE *a;
  219. ITEM *v;
  220. {
  221.     INT i,k,l,r,cmp; PAGE *q,*b; ITEM u; CHAR *t;
  222.  
  223. /*    Search for key x on page a */
  224.  
  225.     if(a==NULL)         /* ITEM with key x is not in tree */
  226.         { 
  227.         ++tokcount; ++nkeys; defkey(&v->KEY,x);
  228.  
  229. #ifdef DIAGNOSE
  230. printf("\n             a ==  null v(=%x)->KEY=%s",v,v->KEY);
  231. #endif
  232.  
  233. #ifdef SPRINT
  234.         v->COUNT=1;
  235. #endif
  236.         v->P=NULL;  return (TRUE) ; /* TRUE means not found */
  237.         }
  238.     else
  239.         { l=0; r=a->M-1;  /* binary array search */
  240.         do {
  241.             k=(l+r)/2;
  242.             cmp= strcmp(x,t=(a->E[k].KEY));
  243.  
  244. #ifdef DIAGNOSE
  245. printf("\ncmp=%d,r=%d,l=%d,a(=%x)->P0=%x/E[k=%d].P=%x/E[k].KEY=%x=%s",
  246.             cmp,r,l,a,a->P0,k,a->E[k].P,t,t );
  247. #endif
  248.  
  249.             if( cmp <= 0) r=k-1;
  250.             if( cmp >= 0) l=k+1;
  251.  
  252.            } while ( r >= l );
  253.  
  254.         if( cmp == 0 ) /* found it, bump counter */
  255.             { ++tokcount;
  256. #ifdef SPRINT
  257.               ++a->E[k].COUNT;
  258. #endif
  259.               return(FALSE); }
  260.  
  261.         else    /* test if item is not on this page   */
  262.             {
  263.             q = ( r < 0 ) ? a->P0 : a->E[r].P;
  264.  
  265.             if( !search(x,q,u) ) return(FALSE);
  266.             }
  267.         }
  268.  
  269. /* ---- insert an item */
  270.  
  271.     if (a->M < NN)
  272.         { /* page not full yet, add to it. 'Bump' items from r+1 to
  273.                             M-1 */
  274.         movmem( a->E[r+1] , a->E[r+2] , sizitem*((a->M++)-r-1) );
  275.         movmem( u , a->E[r+1]  , sizitem );
  276.  
  277.         return(FALSE);
  278.         }
  279.     else
  280.         { /* page full, split it and push center item upward in tree */
  281.         if( (b = alloc(sizpage)) == ERROR )
  282.             { printf("\nOut of memory"); EXIT(0) ; }
  283.  
  284. #ifdef DIAGNOSE
  285. printf("\n\n ******  new node at %x",b);
  286. #endif
  287.  
  288.         if ( r <= NM1 ) /* put new item in old page */
  289.             {
  290.             if ( r == NM1 )  movmem( u , v , sizitem );
  291.             else
  292.                 { /* 'bump' down items from r+2 to N-1 */
  293.  
  294.                 movmem( a->E[NM1] , v , sizitem );
  295.                 movmem( a->E[r+1] , a->E[r+2] ,
  296.                             sizitem*(NM2-r) );
  297.                 movmem( u , a->E[r+1]  , sizitem );
  298.                 }
  299.             movmem( a->E[N] , b->E[0] , sizitem*N );
  300.             }
  301.         else
  302.             {/* move upper N items and new item to new page */
  303.  
  304.             movmem( a->E[N] , v , sizitem ) ;
  305.  
  306.             if( (r -= N) > 0 )    
  307.                 movmem( a->E[NP1] , b->E[0] , sizitem*r );
  308.  
  309.             movmem( u , b->E[r] , sizitem );
  310.  
  311.             if( (i = NM1-r) > 0 )
  312.                 movmem( a->E[NP1+r] , b->E[r+1], sizitem * i );
  313.             }
  314.  
  315.         a->M = b->M = N ; b->P0 = v->P; v->P = b ;
  316.         }
  317.  
  318.     return (TRUE);
  319. }
  320. printtree(p,l)
  321. PAGE *p;
  322. INT l;
  323. {
  324.     INT i,j;  CHAR *t;
  325.  
  326.     if(maxcount <= 0) return;
  327.  
  328.     if ( p != NULL )
  329.         {
  330.  
  331.         printtree(p->P0, l+1 );
  332.  
  333.         for ( i=0; i <= (j=p->M-1) ; ++i )
  334.             { --maxcount;
  335.             printf("\n");
  336. #ifdef SPRINT
  337.             printf(" %d %d ",l,p->E[i].COUNT );
  338. #endif
  339.             prints(p->E[i].KEY);
  340.  
  341.             printtree(p->E[i].P,l+1); 
  342.             }
  343.         }
  344. }
  345. /* defkey allows use of the KEYPTR parameter to specify whether to allocate
  346.    strings to the node which refers to them or to their own locations  */
  347.  
  348. defkey(a,b)
  349. char **a,*b;
  350. {
  351. #ifdef KEYPTR
  352.     if ( (*a=alloc(strlen(b)+1)) == ERROR )
  353.         {printfc("\ninsufficient string storage in defkey\n");EXIT(0);}
  354.     strcpy(*a,b);
  355. #endif
  356. #ifndef KEYPTR
  357.     strcpy(a,b);
  358. #endif
  359. }
  360.  
  361. /* general purpose support programs */
  362.  
  363. trim(strg)
  364. char *strg;
  365. {
  366.     INT l;
  367.  
  368.     l=strlen(strg);
  369.     while ( strg[l] <= ' ' )
  370.         { if( l <= 0 ) break;  strg[l--]='\0'; }
  371.     return(l);
  372. }
  373. prints(str)
  374. char *str;
  375. {
  376.     if(o_flg)
  377.         fputs(str,l_buffer);
  378.     else
  379.         puts(str);        /* and print out the line     */
  380. }
  381. /* Note: The following two functions were obtained from the BDS STDLIB2.C
  382.      file and may be quite dependent on this compiler since the 'C'
  383.      language does specify where arguments are to be found. Their
  384.      purpose is to provide output to one of two special devices based
  385.      on the 'o-flg' switch given at run-time.  */
  386.  
  387. printfc(format)
  388. char *format;
  389. {
  390.     char line[MAXLINE];
  391.     _spr(line,&format);    /* use "_spr" to form the output */
  392.  
  393.     puts(line);        /* and print out the line     */
  394. }
  395. printf(format)
  396. char *format;
  397. {
  398.     char line[MAXLINE];
  399.     _spr(line,&format);    /* use "_spr" to form the output */
  400.  
  401.     prints(line);
  402. }
  403. /*  a special version of fputs to surpress those nasty double '\r's that
  404.     sometimes get in */
  405.  
  406. fputs(s,iobuf)
  407. char *s;
  408. struct _buf *iobuf;
  409. {
  410.     char c;
  411.     while (c = *s++) {
  412.         if (c == '\r' || c == '\0') return;
  413.  
  414.         if (c == '\n') putc('\r',iobuf);
  415.         if (putc(c,iobuf) == ERROR) return ERROR;
  416.     }
  417.     return OK;
  418. }
  419.